/**
 * Copyright (c) 2008, the JUNG Project and the Regents of the University 
 * of California
 * All rights reserved.
 *
 * This software is open-source under the BSD license; see either
 * "license.txt" or
 * http://jung.sourceforge.net/license.txt for a description.
 * Created on Sep 16, 2008
 * 
 */
package edu.uci.ics.jung.algorithms.scoring;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Stack;

import org.apache.commons.collections15.Transformer;
import org.apache.commons.collections15.functors.ConstantTransformer;

import edu.uci.ics.jung.algorithms.util.MapBinaryHeap;
import edu.uci.ics.jung.graph.Graph;
import edu.uci.ics.jung.graph.UndirectedGraph;

/**
 * Computes betweenness centrality for each vertex and edge in the graph.
 * 
 * @see "Ulrik Brandes: A Faster Algorithm for Betweenness Centrality. Journal of Mathematical Sociology 25(2):163-177, 2001."
 */
public class BetweennessCentrality<V, E>
		implements VertexScorer<V, Double>, EdgeScorer<E, Double> {
	protected Graph<V, E> graph;
	protected Map<V, Double> vertex_scores;
	protected Map<E, Double> edge_scores;
	protected Map<V, BetweennessData> vertex_data;

	/**
	 * Calculates betweenness scores based on the all-pairs unweighted shortest
	 * paths in the graph.
	 * 
	 * @param graph
	 *            the graph for which the scores are to be calculated
	 */
	@SuppressWarnings("unchecked")
	public BetweennessCentrality(Graph<V, E> graph) {
		initialize(graph);
		computeBetweenness(new LinkedList<V>(), new ConstantTransformer(1));
	}

	/**
	 * Calculates betweenness scores based on the all-pairs weighted shortest
	 * paths in the graph.
	 * 
	 * <p>
	 * NOTE: This version of the algorithm may not work correctly on all graphs;
	 * we're still working out the bugs. Use at your own risk.
	 * 
	 * @param graph
	 *            the graph for which the scores are to be calculated
	 * @param edge_weights
	 *            the edge weights to be used in the path length calculations
	 */
	public BetweennessCentrality(Graph<V, E> graph,
			Transformer<E, ? extends Number> edge_weights) {
		// reject negative-weight edges up front
		for (E e : graph.getEdges()) {
			double e_weight = edge_weights.transform(e).doubleValue();
			if (e_weight < 0) {
				throw new IllegalArgumentException(
						"Weight for edge '" + e + "' is < 0: " + e_weight);
			}
		}

		initialize(graph);
		computeBetweenness(new MapBinaryHeap<V>(new BetweennessComparator()),
				edge_weights);
	}

	protected void initialize(Graph<V, E> graph) {
		this.graph = graph;
		this.vertex_scores = new HashMap<V, Double>();
		this.edge_scores = new HashMap<E, Double>();
		this.vertex_data = new HashMap<V, BetweennessData>();

		for (V v : graph.getVertices()) {
			this.vertex_scores.put(v, 0.0);
		}

		for (E e : graph.getEdges()) {
			this.edge_scores.put(e, 0.0);
		}
	}

	protected void computeBetweenness(Queue<V> queue,
			Transformer<E, ? extends Number> edge_weights) {
		for (V v : graph.getVertices()) {
			// initialize the betweenness data for this new vertex
			for (V s : graph.getVertices()) {
				this.vertex_data.put(s, new BetweennessData());
			}

			// if (v.equals(new Integer(0)))
			// System.out.println("pause");

			vertex_data.get(v).numSPs = 1;
			vertex_data.get(v).distance = 0;

			Stack<V> stack = new Stack<V>();
			// Buffer<V> queue = new UnboundedFifoBuffer<V>();
			// queue.add(v);
			queue.offer(v);

			while (!queue.isEmpty()) {
				// V w = queue.remove();
				V w = queue.poll();
				stack.push(w);
				BetweennessData w_data = vertex_data.get(w);

				for (E e : graph.getOutEdges(w)) {
					// TODO (jrtom): change this to getOtherVertices(w, e)
					V x = graph.getOpposite(w, e);
					if (x.equals(w)) {
						continue;
					}
					double wx_weight = edge_weights.transform(e).doubleValue();

					// for(V x : graph.getSuccessors(w))
					// {
					// if (x.equals(w))
					// continue;

					// FIXME: the other problem is that I need to
					// keep putting the neighbors of things we've just
					// discovered in the queue, if they're undiscovered or
					// at greater distance.

					// FIXME: this is the problem, right here, I think:
					// need to update position in queue if distance changes
					// (which can only happen with weighted edges).
					// for each outgoing edge e from w, get other end x
					// if x not already visited (dist x < 0)
					// set x's distance to w's dist + edge weight
					// add x to queue; pri in queue is x's dist
					// if w's dist + edge weight < x's dist
					// update x's dist
					// update x in queue (MapBinaryHeap)
					// clear x's incoming edge list
					// if w's dist + edge weight = x's dist
					// add e to x's incoming edge list

					BetweennessData x_data = vertex_data.get(x);
					double x_potential_dist = w_data.distance + wx_weight;

					if (x_data.distance < 0) {
						// queue.add(x);
						// vertex_data.get(x).distance =
						// vertex_data.get(w).distance + 1;
						x_data.distance = x_potential_dist;
						queue.offer(x);
					}

					// note:
					// (1) this can only happen with weighted edges
					// (2) x's SP count and incoming edges are updated below
					if (x_data.distance > x_potential_dist) {
						x_data.distance = x_potential_dist;
						// invalidate previously identified incoming edges
						// (we have a new shortest path distance to x)
						x_data.incomingEdges.clear();
						// update x's position in queue
						((MapBinaryHeap<V>) queue).update(x);
					}
					// if (vertex_data.get(x).distance ==
					// vertex_data.get(w).distance + 1)
					//
					// if (x_data.distance == x_potential_dist)
					// {
					// x_data.numSPs += w_data.numSPs;
					//// vertex_data.get(x).predecessors.add(w);
					// x_data.incomingEdges.add(e);
					// }
				}
				for (E e : graph.getOutEdges(w)) {
					V x = graph.getOpposite(w, e);
					if (x.equals(w)) {
						continue;
					}
					double e_weight = edge_weights.transform(e).doubleValue();
					BetweennessData x_data = vertex_data.get(x);
					double x_potential_dist = w_data.distance + e_weight;
					if (x_data.distance == x_potential_dist) {
						x_data.numSPs += w_data.numSPs;
						// vertex_data.get(x).predecessors.add(w);
						x_data.incomingEdges.add(e);
					}
				}
			}
			while (!stack.isEmpty()) {
				V x = stack.pop();

				// for (V w : vertex_data.get(x).predecessors)
				for (E e : vertex_data.get(x).incomingEdges) {
					V w = graph.getOpposite(x, e);
					double partialDependency = vertex_data.get(w).numSPs
							/ vertex_data.get(x).numSPs
							* (1.0 + vertex_data.get(x).dependency);
					vertex_data.get(w).dependency += partialDependency;
					// E w_x = graph.findEdge(w, x);
					// double w_x_score = edge_scores.get(w_x).doubleValue();
					// w_x_score += partialDependency;
					// edge_scores.put(w_x, w_x_score);
					double e_score = edge_scores.get(e).doubleValue();
					edge_scores.put(e, e_score + partialDependency);
				}
				if (!x.equals(v)) {
					double x_score = vertex_scores.get(x).doubleValue();
					x_score += vertex_data.get(x).dependency;
					vertex_scores.put(x, x_score);
				}
			}
		}

		if (graph instanceof UndirectedGraph) {
			for (V v : graph.getVertices()) {
				double v_score = vertex_scores.get(v).doubleValue();
				v_score /= 2.0;
				vertex_scores.put(v, v_score);
			}
			for (E e : graph.getEdges()) {
				double e_score = edge_scores.get(e).doubleValue();
				e_score /= 2.0;
				edge_scores.put(e, e_score);
			}
		}

		vertex_data.clear();
	}

	// protected void computeWeightedBetweenness(Transformer<E, ? extends
	// Number> edge_weights)
	// {
	// for (V v : graph.getVertices())
	// {
	// // initialize the betweenness data for this new vertex
	// for (V s : graph.getVertices())
	// this.vertex_data.put(s, new BetweennessData());
	// vertex_data.get(v).numSPs = 1;
	// vertex_data.get(v).distance = 0;
	//
	// Stack<V> stack = new Stack<V>();
	//// Buffer<V> queue = new UnboundedFifoBuffer<V>();
	// SortedSet<V> pqueue = new TreeSet<V>(new BetweennessComparator());
	//// queue.add(v);
	// pqueue.add(v);
	//
	//// while (!queue.isEmpty())
	// while (!pqueue.isEmpty())
	// {
	//// V w = queue.remove();
	// V w = pqueue.first();
	// pqueue.remove(w);
	// stack.push(w);
	//
	//// for(V x : graph.getSuccessors(w))
	// for (E e : graph.getOutEdges(w))
	// {
	// // TODO (jrtom): change this to getOtherVertices(w, e)
	// V x = graph.getOpposite(w, e);
	// if (x.equals(w))
	// continue;
	// double e_weight = edge_weights.transform(e).doubleValue();
	//
	// if (vertex_data.get(x).distance < 0)
	// {
	//// queue.add(x);
	// pqueue.add(v);
	//// vertex_data.get(x).distance = vertex_data.get(w).distance + 1;
	// vertex_data.get(x).distance =
	// vertex_data.get(w).distance + e_weight;
	// }
	//
	//// if (vertex_data.get(x).distance == vertex_data.get(w).distance + 1)
	// if (vertex_data.get(x).distance ==
	// vertex_data.get(w).distance + e_weight)
	// {
	// vertex_data.get(x).numSPs += vertex_data.get(w).numSPs;
	// vertex_data.get(x).predecessors.add(w);
	// }
	// }
	// }
	// updateScores(v, stack);
	// }
	//
	// if(graph instanceof UndirectedGraph)
	// adjustUndirectedScores();
	//
	// vertex_data.clear();
	// }

	@Override
	public Double getVertexScore(V v) {
		return vertex_scores.get(v);
	}

	@Override
	public Double getEdgeScore(E e) {
		return edge_scores.get(e);
	}

	private class BetweennessData {
		double distance;
		double numSPs;
		// List<V> predecessors;
		List<E> incomingEdges;
		double dependency;

		BetweennessData() {
			distance = -1;
			numSPs = 0;
			// predecessors = new ArrayList<V>();
			incomingEdges = new ArrayList<E>();
			dependency = 0;
		}

		@Override
		public String toString() {
			return "[d:" + distance + ", sp:" + numSPs + ", p:" + incomingEdges
					+ ", d:" + dependency + "]\n";
			// ", p:" + predecessors + ", d:" + dependency + "]\n";
		}
	}

	private class BetweennessComparator implements Comparator<V> {
		@Override
		public int compare(V v1, V v2) {
			return vertex_data.get(v1).distance > vertex_data.get(v2).distance
					? 1 : -1;
		}
	}
}
